package com.zhugang.week12;

/**
 * @program algorithms
 * @description: maxProfit
 * @author: chanzhugang
 * @create: 2022/09/08 11:45
 */
public class MaxProfit {

    /**
     * 121 买卖股票的最佳时机
     * 前缀后缀统计: O(n)
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        // 后缀统计
        int n = prices.length;

        int[] max = new int[n];
        int curMax = 0;
        for (int i = n - 1; i >= 0; i--) {
            max[i] = curMax;
            // 后缀统计最大值放数组里
            curMax = Math.max(curMax, prices[i]);
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            // i对应的最大利润
            result = Math.max(result, max[i] - prices[i]);
        }
        return result;
    }
}